import random
import numpy as np
import csv
import statistics
import matplotlib.pyplot as plt

from ArrayChebyshev import ArrayChebyshev
from util.util_analysis_line import msll_line



def psl_plane(NA, NE, theta0, phi0, pattern_dbw):
    temp1 = pattern_dbw[:, round(NE * ((np.pi / 2 + theta0) / np.pi))]
    temp2 = pattern_dbw[round(NA * ((np.pi / 2 + phi0) / np.pi)), :]
    # print("temp1:", temp1)
    # print("temp2:", temp2)
    msll_arr_w_1 = msll_line(temp1)
    msll_arr_w_2 = msll_line(temp2)
    msll_arr_w = max(msll_arr_w_1, msll_arr_w_2)
    #
    return msll_arr_w


def save_csv(data, file_path):
    # 指定CSV文件路径
    # file_path = 'data.csv'
    # 保存数据到CSV文件
    with open(file_path, mode='w', newline='') as file:
        writer = csv.writer(file)
        writer.writerows(data)
    print("数据已成功保存到CSV文件:", file_path)


def calculate_statistics(lst):
    maximum = max(lst)
    minimum = min(lst)
    average = sum(lst) / len(lst)
    standard_deviation = statistics.stdev(lst)
    return maximum, minimum, average, standard_deviation



class SubarrayGA():
    K = 9
    lambda_ = 1  # 波长
    d = 0.5  # 阵元间隔
    Ny = 40  # 方位阵元个数
    Nz = 40  # 俯仰阵元个数
    phi0 = 0  # 方位指向
    theta0 = 0  # 俯仰指向
    eps = 0.0001  # 底电平
    NA = 360  # 方位角度采样
    NE = 360  # 俯仰角度采样
    SLL = -60
    weights = None
    arrayCheby = None


    def __average_values_by_indices(self, weights, weights_indices):
        """
        根据weights_indices中的索引，对weights中的值进行分组平均，
        并将结果存储到一个新的与weights同尺寸的数组weights_sub中。
        参数:
        weights -- 类型为np.array的二维数组，尺寸为MxN
        weights_indices -- 与weights同尺寸的二维数组，存储了每个元素应归属的组的索引
        返回:
        weights_sub -- 与weights同尺寸的二维数组，其中每个值是对应位置weights中相同索引值的平均值
        """
        # 获取weights的尺寸
        M, N = weights.shape
        # 初始化weights_sub为weights的形状，初始填充NaN以方便后续检查是否所有索引都被处理
        weights_sub = np.full_like(weights, np.nan)
        # 遍历所有可能的索引值
        unique_indices = np.unique(weights_indices)
        for index in unique_indices:
            # 找到weights_indices中等于当前index的所有位置
            mask = weights_indices == index
            # 根据位置mask选择weights中的值，然后计算这些值的平均值
            avg_value = np.mean(weights[mask])
            # 将平均值赋给weights_sub中对应的位置
            weights_sub[mask] = avg_value
        # 检查weights_sub中是否还有NaN值，确保所有位置都被正确处理
        if np.isnan(weights_sub).any():
            raise ValueError("有些索引可能没有对应的值进行平均，请检查weights_indices是否包含了所有必要的索引。")
        return weights_sub


    # 适应度函数
    def __fitness(self, individual):
        # weights_indices = individual.reshape(self.weights.shape)
        weights_indices = individual
        weights_sub = self.__average_values_by_indices(self.weights, weights_indices)
        pattern_dbw, theta, phi = self.getPatternDbPlane(weights_sub)
        msll = psl_plane(self.NA, self.NE, self.theta0, self.phi0, pattern_dbw)
        return msll


    # 选择操作：基于个体适应度的轮盘赌选择
    def __select(self, population, fitnesses):
        total_fitness = sum(fitnesses)
        selection_probs = [f / total_fitness for f in fitnesses]
        return population[np.random.choice(len(population), p=selection_probs)]


    # 交叉操作：单点交叉
    def __crossover(self, ind1_2d, ind2_2d):
        ind1 = ind1_2d.flatten()
        ind2 = ind2_2d.flatten()
        point = random.randint(1, len(ind1) - 2)
        # new_ind1 = ind1[:point] + ind2[point:]
        # new_ind2 = ind2[:point] + ind1[point:]
        new_ind1 = np.concatenate((ind1[:point], ind2[point:]))
        new_ind2 = np.concatenate((ind2[:point], ind1[point:]))
        new_ind1_2d = new_ind1.reshape(self.weights.shape)
        new_ind2_2d = new_ind2.reshape(self.weights.shape)
        return (new_ind1_2d, new_ind2_2d)


    # 变异操作：随机翻转某个位置的值
    def __mutate(self, individual_2d):
        individual = individual_2d.flatten()
        point = random.randint(0, len(individual) - 1)
        individual[point] = random.randint(0, self.K-1)
        return individual.reshape(self.weights.shape)


    # 创建初始种群 -- 全部随机
    def __create_population_random(self, count):
        M, N = self.weights.shape
        return [np.random.randint(self.K-1, size=(M, N)) for _ in range(count)]


    def __create_population_nm(self, count):
        arr_item = [[0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0],
                     [0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0],
                     [1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 3, 2, 2, 1, 1],
                     [1, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 1],
                     [2, 2, 3, 4, 6, 7, 7, 8, 7, 7, 6, 4, 3, 2, 2],
                     [2, 2, 4, 5, 7, 8, 8, 8, 8, 8, 7, 5, 4, 2, 2],
                     [2, 3, 4, 6, 7, 8, 9, 9, 9, 8, 7, 6, 4, 3, 2],
                     [2, 3, 4, 6, 8, 8, 9, 9, 9, 8, 8, 6, 4, 3, 2],
                     [2, 3, 4, 6, 7, 8, 9, 9, 9, 8, 7, 6, 4, 3, 2],
                     [2, 2, 4, 5, 7, 8, 8, 8, 8, 8, 7, 5, 4, 2, 2],
                     [2, 2, 3, 4, 6, 7, 7, 8, 7, 7, 6, 4, 3, 2, 2],
                     [1, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 1],
                     [1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 3, 2, 2, 1, 1],
                     [0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0],
                     [0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0]]
        arr_item = np.array(arr_item)
        return [arr_item for _ in range(count)]


    def __create_population_nm_mutate(self, count):
        arr_item_list = []
        # arr_item = [[0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0],
        #              [0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0],
        #              [1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 3, 2, 2, 1, 1],
        #              [1, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 1],
        #              [2, 2, 3, 4, 6, 7, 7, 8, 7, 7, 6, 4, 3, 2, 2],
        #              [2, 2, 4, 5, 7, 8, 8, 8, 8, 8, 7, 5, 4, 2, 2],
        #              [2, 3, 4, 6, 7, 8, 9, 9, 9, 8, 7, 6, 4, 3, 2],
        #              [2, 3, 4, 6, 8, 8, 9, 9, 9, 8, 8, 6, 4, 3, 2],
        #              [2, 3, 4, 6, 7, 8, 9, 9, 9, 8, 7, 6, 4, 3, 2],
        #              [2, 2, 4, 5, 7, 8, 8, 8, 8, 8, 7, 5, 4, 2, 2],
        #              [2, 2, 3, 4, 6, 7, 7, 8, 7, 7, 6, 4, 3, 2, 2],
        #              [1, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 1],
        #              [1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 3, 2, 2, 1, 1],
        #              [0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0],
        #              [0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0]]
        # 以下40x40-10-sll60
        # arr_item  = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 7, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 9, 8, 8, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 8, 8, 7, 7, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 8, 8, 7, 7, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 9, 8, 8, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 7, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0],
        #              [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        #              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
        # 以下40x40-25-sll60
        # arr_item  = [[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  4,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  4,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  8,  8,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  5,  6,  7,  8,  8,  9,  9, 10, 10, 10, 10,  9,  9,  8,  8,  7,  6,  5,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  6,  6,  7,  8,  9, 10, 11, 11, 12, 12, 12, 12, 11, 11, 10,  9,  8,  7,  6,  6,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  8,  9, 10, 11, 12, 12, 13, 14, 14, 14, 14, 13, 12, 12, 11, 10,  9,  8,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 15, 14, 13, 12, 11, 10,  9,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  3,  3,  5,  6,  7,  8, 10, 11, 13, 14, 15, 16, 17, 17, 18, 18, 17, 17, 16, 15, 14, 13, 11, 10,  8,  7,  6,  5,  3,  3,  2,  1,  1,  0,  0],
        #              [ 0,  1,  1,  1,  2,  3,  4,  5,  6,  8,  9, 11, 12, 14, 15, 17, 18, 19, 19, 20, 20, 19, 19, 18, 17, 15, 14, 12, 11,  9,  8,  6,  5,  4,  3,  2,  1,  1,  1,  0],
        #              [ 0,  1,  1,  2,  2,  3,  4,  5,  7,  8, 10, 12, 13, 15, 17, 18, 19, 20, 21, 21, 21, 21, 20, 19, 18, 17, 15, 13, 12, 10,  8,  7,  5,  4,  3,  2,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  2,  3,  4,  6,  7,  9, 11, 12, 14, 16, 18, 19, 21, 22, 22, 23, 23, 22, 22, 21, 19, 18, 16, 14, 12, 11,  9,  7,  6,  4,  3,  2,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8,  9, 11, 13, 15, 17, 19, 20, 22, 23, 23, 23, 23, 23, 23, 22, 20, 19, 17, 15, 13, 11,  9,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8, 10, 12, 14, 16, 17, 19, 21, 22, 23, 24, 24, 24, 24, 23, 22, 21, 19, 17, 16, 14, 12, 10,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8, 10, 12, 14, 16, 18, 20, 21, 23, 23, 24, 24, 24, 24, 23, 23, 21, 20, 18, 16, 14, 12, 10,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8, 10, 12, 14, 16, 18, 20, 21, 23, 23, 24, 24, 24, 24, 23, 23, 21, 20, 18, 16, 14, 12, 10,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8, 10, 12, 14, 16, 17, 19, 21, 22, 23, 24, 24, 24, 24, 23, 22, 21, 19, 17, 16, 14, 12, 10,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  3,  4,  5,  6,  8,  9, 11, 13, 15, 17, 19, 20, 22, 23, 23, 23, 23, 23, 23, 22, 20, 19, 17, 15, 13, 11,  9,  8,  6,  5,  4,  3,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  2,  3,  4,  6,  7,  9, 11, 12, 14, 16, 18, 19, 21, 22, 22, 23, 23, 22, 22, 21, 19, 18, 16, 14, 12, 11,  9,  7,  6,  4,  3,  2,  2,  1,  1,  0],
        #              [ 0,  1,  1,  2,  2,  3,  4,  5,  7,  8, 10, 12, 13, 15, 17, 18, 19, 20, 21, 21, 21, 21, 20, 19, 18, 17, 15, 13, 12, 10,  8,  7,  5,  4,  3,  2,  2,  1,  1,  0],
        #              [ 0,  1,  1,  1,  2,  3,  4,  5,  6,  8,  9, 11, 12, 14, 15, 17, 18, 19, 19, 20, 20, 19, 19, 18, 17, 15, 14, 12, 11,  9,  8,  6,  5,  4,  3,  2,  1,  1,  1,  0],
        #              [ 0,  0,  1,  1,  2,  3,  3,  5,  6,  7,  8, 10, 11, 13, 14, 15, 16, 17, 17, 18, 18, 17, 17, 16, 15, 14, 13, 11, 10,  8,  7,  6,  5,  3,  3,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 15, 14, 13, 12, 11, 10,  9,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  8,  9, 10, 11, 12, 12, 13, 14, 14, 14, 14, 13, 12, 12, 11, 10,  9,  8,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  6,  6,  7,  8,  9, 10, 11, 11, 12, 12, 12, 12, 11, 11, 10,  9,  8,  7,  6,  6,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  5,  6,  7,  8,  8,  9,  9, 10, 10, 10, 10,  9,  9,  8,  8,  7,  6,  5,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  8,  8,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  4,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  4,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]]
        # 以下40x40-16-sll60
        # arr_item  = [[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  4,  3,  2,  2,  1,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  3,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  3,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  6,  7,  8,  9,  9, 10, 10, 10, 10, 10, 10,  9,  9,  8,  7,  6,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  4,  5,  6,  7,  8,  9, 10, 10, 11, 11, 11, 11, 11, 11, 10, 10,  9,  8,  7,  6,  5,  4,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 11, 12, 12, 13, 13, 12, 12, 11, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  7,  9, 10, 11, 12, 12, 13, 13, 14, 14, 13, 13, 12, 12, 11, 10,  9,  7,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 14, 14, 14, 14, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8, 10, 11, 12, 13, 14, 14, 15, 15, 15, 15, 14, 14, 13, 12, 11, 10,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  9, 10, 11, 12, 13, 14, 15, 15, 15, 15, 15, 15, 14, 13, 12, 11, 10,  9,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  8,  9, 10, 11, 13, 14, 14, 15, 15, 15, 15, 15, 15, 14, 14, 13, 11, 10,  9,  8,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  8,  9, 10, 11, 13, 14, 14, 15, 15, 15, 15, 15, 15, 14, 14, 13, 11, 10,  9,  8,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  9, 10, 11, 12, 13, 14, 15, 15, 15, 15, 15, 15, 14, 13, 12, 11, 10,  9,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8, 10, 11, 12, 13, 14, 14, 15, 15, 15, 15, 14, 14, 13, 12, 11, 10,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 14, 14, 14, 14, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  7,  9, 10, 11, 12, 12, 13, 13, 14, 14, 13, 13, 12, 12, 11, 10,  9,  7,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 11, 12, 12, 13, 13, 12, 12, 11, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  1,  1,  1,  2,  2,  3,  4,  4,  5,  6,  7,  8,  9, 10, 10, 11, 11, 11, 11, 11, 11, 10, 10,  9,  8,  7,  6,  5,  4,  4,  3,  2,  2,  1,  1,  1,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  3,  3,  4,  5,  6,  6,  7,  8,  9,  9, 10, 10, 10, 10, 10, 10,  9,  9,  8,  7,  6,  6,  5,  4,  3,  3,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  2,  2,  3,  3,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  3,  3,  2,  2,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  1,  1,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  4,  3,  2,  2,  1,  1,  1,  1,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  1,  1,  1,  1,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        #              [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]]
        # 以下40x40-9-sll60
        arr_item  = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 7, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 7, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 6, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 7, 7, 7, 6, 5, 5, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 7, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
        # arr_item  = [[ 3,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  6,  6,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  3],
        #              [ 1,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  1],
        #              [ 1,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  1],
        #              [ 1,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  1],
        #              [ 2,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  0,  2],
        #              [ 2,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  2],
        #              [ 2,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  4,  4,  4,  4,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  2],
        #              [ 3,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  3],
        #              [ 3,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  3],
        #              [ 3,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  7,  6,  6,  6,  6,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  3],
        #              [ 4,  1,  2,  2,  3,  3,  3,  4,  4,  5,  5,  6,  6,  6,  7,  7,  7,  7,  8,  8,  8,  8,  7,  7,  7,  7,  6,  6,  6,  5,  5,  4,  4,  3,  3,  3,  2,  2,  1,  4],
        #              [ 4,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  1,  4],
        #              [ 4,  2,  2,  2,  3,  3,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  8,  9,  9,  9,  9,  9,  9,  8,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  3,  3,  2,  2,  2,  4],
        #              [ 5,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  3,  4,  5,  5,  6,  6,  7,  8,  8,  9,  9,  9,  9,  9, 10, 10, 10, 10,  9,  9,  9,  9,  9,  8,  8,  7,  6,  6,  5,  5,  4,  3,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  4,  4,  5,  5,  6,  7,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  7,  6,  5,  5,  4,  4,  3,  2,  2,  5],
        #              [ 5,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  9,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  9,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  5],
        #              [ 5,  2,  3,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  3,  2,  5],
        #              [ 6,  2,  3,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  3,  2,  6],
        #              [ 6,  2,  3,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  3,  2,  6],
        #              [ 5,  2,  3,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  3,  2,  5],
        #              [ 5,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  9,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  9,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  5],
        #              [ 5,  2,  2,  3,  4,  4,  5,  5,  6,  7,  7,  8,  8,  9,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  9,  8,  8,  7,  7,  6,  5,  5,  4,  4,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  3,  4,  5,  5,  6,  6,  7,  8,  8,  9,  9,  9,  9,  9, 10, 10, 10, 10,  9,  9,  9,  9,  9,  8,  8,  7,  6,  6,  5,  5,  4,  3,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  3,  2,  2,  5],
        #              [ 5,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  8,  8,  7,  7,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  5],
        #              [ 4,  2,  2,  2,  3,  3,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  8,  9,  9,  9,  9,  9,  9,  8,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  3,  3,  2,  2,  2,  4],
        #              [ 4,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  7,  7,  7,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  1,  4],
        #              [ 4,  1,  2,  2,  3,  3,  3,  4,  4,  5,  5,  6,  6,  6,  7,  7,  7,  7,  8,  8,  8,  8,  7,  7,  7,  7,  6,  6,  6,  5,  5,  4,  4,  3,  3,  3,  2,  2,  1,  4],
        #              [ 3,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  7,  6,  6,  6,  6,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  3],
        #              [ 3,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  3],
        #              [ 3,  1,  1,  1,  2,  2,  2,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  2,  2,  2,  1,  1,  1,  3],
        #              [ 2,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  4,  4,  4,  4,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  2],
        #              [ 2,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  2],
        #              [ 2,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  1,  1,  1,  1,  0,  2],
        #              [ 1,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  1],
        #              [ 1,  0,  0,  0,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  0,  0,  0,  1],
        #              [ 1,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  1],
        #              [ 3,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  5,  5,  5,  6,  6,  5,  5,  5,  5,  5,  5,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  3]]
        # arr_item  = [[ 6,  2,  2,  3,  4,  5,  5,  6,  7,  8,  9,  9, 10, 11, 11, 12, 12, 12, 12, 13, 13, 12, 12, 12, 12, 11, 11, 10,  9,  9,  8,  7,  6,  5,  5,  4,  3,  2,  2,  6],
        #              [ 2,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  4,  5,  5,  5,  5,  5,  5,  4,  4,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  2],
        #              [ 2,  0,  1,  1,  1,  2,  2,  3,  3,  3,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  4,  4,  3,  3,  3,  2,  2,  1,  1,  1,  0,  2],
        #              [ 3,  1,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  6,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  1,  1,  1,  3],
        #              [ 4,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  8,  8,  9,  9,  9,  9,  8,  8,  8,  8,  7,  7,  6,  6,  5,  5,  4,  4,  3,  2,  2,  1,  1,  4],
        #              [ 5,  1,  2,  2,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  2,  2,  1,  5],
        #              [ 5,  2,  2,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9, 10, 10, 11, 11, 11, 11, 12, 12, 11, 11, 11, 11, 10, 10,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  2,  2,  5],
        #              [ 6,  2,  3,  3,  4,  5,  6,  6,  7,  8,  9, 10, 10, 11, 12, 12, 12, 13, 13, 13, 13, 13, 13, 12, 12, 12, 11, 10, 10,  9,  8,  7,  6,  6,  5,  4,  3,  3,  2,  6],
        #              [ 7,  2,  3,  4,  5,  6,  6,  7,  8,  9, 10, 11, 12, 12, 13, 13, 14, 14, 14, 15, 15, 14, 14, 14, 13, 13, 12, 12, 11, 10,  9,  8,  7,  6,  6,  5,  4,  3,  2,  7],
        #              [ 8,  3,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 13, 14, 15, 15, 16, 16, 16, 16, 16, 16, 15, 15, 14, 13, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  3,  8],
        #              [ 9,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 17, 17, 17, 17, 17, 17, 17, 16, 15, 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  9],
        #              [ 9,  3,  4,  5,  6,  7,  8, 10, 11, 12, 13, 14, 15, 16, 17, 17, 18, 18, 19, 19, 19, 19, 18, 18, 17, 17, 16, 15, 14, 13, 12, 11, 10,  8,  7,  6,  5,  4,  3,  9],
        #              [10,  4,  5,  6,  7,  8,  9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 20, 20, 20, 20, 20, 19, 19, 18, 17, 16, 15, 14, 13, 12, 10,  9,  8,  7,  6,  5,  4, 10],
        #              [11,  4,  5,  6,  7,  8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 20, 21, 21, 21, 21, 21, 21, 20, 20, 19, 18, 17, 16, 15, 13, 12, 11, 10,  8,  7,  6,  5,  4, 11],
        #              [11,  4,  5,  6,  8,  9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 21, 21, 22, 22, 22, 22, 22, 22, 21, 21, 20, 19, 18, 17, 15, 14, 13, 12, 10,  9,  8,  6,  5,  4, 11],
        #              [12,  4,  5,  7,  8,  9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 21, 22, 23, 23, 23, 23, 23, 23, 22, 21, 21, 20, 19, 17, 16, 15, 13, 12, 11,  9,  8,  7,  5,  4, 12],
        #              [12,  4,  6,  7,  8, 10, 11, 12, 14, 15, 17, 18, 19, 20, 21, 22, 23, 23, 23, 23, 23, 23, 23, 23, 22, 21, 20, 19, 18, 17, 15, 14, 12, 11, 10,  8,  7,  6,  4, 12],
        #              [12,  5,  6,  7,  8, 10, 11, 13, 14, 16, 17, 18, 20, 21, 22, 23, 23, 23, 24, 24, 24, 24, 23, 23, 23, 22, 21, 20, 18, 17, 16, 14, 13, 11, 10,  8,  7,  6,  5, 12],
        #              [12,  5,  6,  7,  9, 10, 11, 13, 14, 16, 17, 19, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 24, 23, 23, 22, 21, 20, 19, 17, 16, 14, 13, 11, 10,  9,  7,  6,  5, 12],
        #              [13,  5,  6,  7,  9, 10, 12, 13, 15, 16, 17, 19, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 24, 23, 23, 22, 21, 20, 19, 17, 16, 15, 13, 12, 10,  9,  7,  6,  5, 13],
        #              [13,  5,  6,  7,  9, 10, 12, 13, 15, 16, 17, 19, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 24, 23, 23, 22, 21, 20, 19, 17, 16, 15, 13, 12, 10,  9,  7,  6,  5, 13],
        #              [12,  5,  6,  7,  9, 10, 11, 13, 14, 16, 17, 19, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 24, 23, 23, 22, 21, 20, 19, 17, 16, 14, 13, 11, 10,  9,  7,  6,  5, 12],
        #              [12,  5,  6,  7,  8, 10, 11, 13, 14, 16, 17, 18, 20, 21, 22, 23, 23, 23, 24, 24, 24, 24, 23, 23, 23, 22, 21, 20, 18, 17, 16, 14, 13, 11, 10,  8,  7,  6,  5, 12],
        #              [12,  4,  6,  7,  8, 10, 11, 12, 14, 15, 17, 18, 19, 20, 21, 22, 23, 23, 23, 23, 23, 23, 23, 23, 22, 21, 20, 19, 18, 17, 15, 14, 12, 11, 10,  8,  7,  6,  4, 12],
        #              [12,  4,  5,  7,  8,  9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 21, 22, 23, 23, 23, 23, 23, 23, 22, 21, 21, 20, 19, 17, 16, 15, 13, 12, 11,  9,  8,  7,  5,  4, 12],
        #              [11,  4,  5,  6,  8,  9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 21, 21, 22, 22, 22, 22, 22, 22, 21, 21, 20, 19, 18, 17, 15, 14, 13, 12, 10,  9,  8,  6,  5,  4, 11],
        #              [11,  4,  5,  6,  7,  8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 20, 21, 21, 21, 21, 21, 21, 20, 20, 19, 18, 17, 16, 15, 13, 12, 11, 10,  8,  7,  6,  5,  4, 11],
        #              [10,  4,  5,  6,  7,  8,  9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 20, 20, 20, 20, 20, 19, 19, 18, 17, 16, 15, 14, 13, 12, 10,  9,  8,  7,  6,  5,  4, 10],
        #              [ 9,  3,  4,  5,  6,  7,  8, 10, 11, 12, 13, 14, 15, 16, 17, 17, 18, 18, 19, 19, 19, 19, 18, 18, 17, 17, 16, 15, 14, 13, 12, 11, 10,  8,  7,  6,  5,  4,  3,  9],
        #              [ 9,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 17, 17, 17, 17, 17, 17, 17, 16, 15, 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  9],
        #              [ 8,  3,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 13, 14, 15, 15, 16, 16, 16, 16, 16, 16, 15, 15, 14, 13, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  3,  8],
        #              [ 7,  2,  3,  4,  5,  6,  6,  7,  8,  9, 10, 11, 12, 12, 13, 13, 14, 14, 14, 15, 15, 14, 14, 14, 13, 13, 12, 12, 11, 10,  9,  8,  7,  6,  6,  5,  4,  3,  2,  7],
        #              [ 6,  2,  3,  3,  4,  5,  6,  6,  7,  8,  9, 10, 10, 11, 12, 12, 12, 13, 13, 13, 13, 13, 13, 12, 12, 12, 11, 10, 10,  9,  8,  7,  6,  6,  5,  4,  3,  3,  2,  6],
        #              [ 5,  2,  2,  3,  4,  4,  5,  6,  6,  7,  8,  8,  9, 10, 10, 11, 11, 11, 11, 12, 12, 11, 11, 11, 11, 10, 10,  9,  8,  8,  7,  6,  6,  5,  4,  4,  3,  2,  2,  5],
        #              [ 5,  1,  2,  2,  3,  4,  4,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 10, 10, 10, 10, 10, 10,  9,  9,  8,  8,  7,  7,  6,  6,  5,  4,  4,  3,  2,  2,  1,  5],
        #              [ 4,  1,  1,  2,  2,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  8,  8,  9,  9,  9,  9,  8,  8,  8,  8,  7,  7,  6,  6,  5,  5,  4,  4,  3,  2,  2,  1,  1,  4],
        #              [ 3,  1,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  6,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  6,  6,  6,  5,  5,  4,  4,  3,  3,  2,  2,  1,  1,  1,  3],
        #              [ 2,  0,  1,  1,  1,  2,  2,  3,  3,  3,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  4,  4,  3,  3,  3,  2,  2,  1,  1,  1,  0,  2],
        #              [ 2,  0,  0,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  4,  5,  5,  5,  5,  5,  5,  4,  4,  4,  4,  4,  3,  3,  3,  2,  2,  2,  1,  1,  1,  0,  0,  2],
        #              [ 6,  2,  2,  3,  4,  5,  5,  6,  7,  8,  9,  9, 10, 11, 11, 12, 12, 12, 12, 13, 13, 12, 12, 12, 12, 11, 11, 10,  9,  9,  8,  7,  6,  5,  5,  4,  3,  2,  2,  6]]
        arr_item = np.array(arr_item)
        for _ in range(count):
            tmp = arr_item.copy()
            for i in range(random.randint(0, 20)):
                tmp = self.__mutate(tmp)
            arr_item_list.append(tmp)
        return arr_item_list



    def __init__(self, lambda_, Ny, Nz, d, phi0, theta0, NA, NE, eps, K):
        self.K = K
        self.lambda_ = lambda_  # 波长
        self.d = d  # 阵元间隔
        self.Ny = Ny  # 方位阵元个数
        self.Nz = Nz  # 俯仰阵元个数
        self.phi0 = phi0  # 方位指向
        self.theta0 = theta0  # 俯仰指向
        self.eps = eps  # 底电平
        self.NA = NA  # 方位角度采样
        self.NE = NE  # 俯仰角度采样
        self.SLL = SLL
        self.arrayCheby = ArrayChebyshev()


    # 遗传算法主体函数 -- GA方式子阵划分
    def parse(self, population_size=3, generations=3, mutation_rate=0.01):
        # 1.设置基于切比雪夫的幅度
        self.weights = self.arrayCheby.getChebyshevPlane(self.Ny, self.Nz, self.SLL)
        #
        # population = self.__create_population_random(population_size)
        # population = self.__create_population_nm(population_size)
        population = self.__create_population_nm_mutate(population_size)
        # best_individual = population[0]
        #
        best_all_weight = population[0]
        best_all_fitness = 0
        #
        for generation in range(generations):
            # 计算适应度
            fitnesses = [self.__fitness(individual) for individual in population]

            # 选择最佳解
            best_individual = population[np.argmin(fitnesses)]
            best_fitness = min(fitnesses)

            if best_fitness < best_all_fitness:
                best_all_fitness = best_fitness
                best_all_weight = best_individual.copy()

            print(f"Generation {generation} best fitness: {best_fitness} best_all_weight: {best_all_fitness}")

            # 判断是否找到满足条件的解
            if best_fitness == self.SLL:
                break

            # 选择和繁殖产生新一代
            new_population = []
            for _ in range(population_size // 2):
                parent1 = self.__select(population, fitnesses)
                parent2 = self.__select(population, fitnesses)
                child1, child2 = self.__crossover(parent1, parent2)

                if random.random() < mutation_rate:
                    child1 = self.__mutate(child1)
                if random.random() < mutation_rate:
                    child2 = self.__mutate(child2)

                new_population.extend([child1, child2])

            population = new_population

        # best_all_weight = self.__average_values_by_indices(self.weights, best_all_weight)

        return self.weights, best_all_weight


    # 根据切比雪夫振幅, 计算方向图Pattern - 面阵
    def getPatternDbPlane(self, weights):
        phi = np.linspace(-np.pi / 2, np.pi / 2, self.NA)
        theta = np.linspace(-np.pi / 2, np.pi / 2, self.NE)
        aa = np.arange(0, self.d * self.Ny, self.d)
        bb = np.arange(0, self.d * self.Nz, self.d)
        DD1 = np.repeat(aa[:, np.newaxis], self.Nz, axis=1)
        DD2 = np.repeat(bb[np.newaxis, :], self.Ny, axis=0)
        DD = DD1 + 1j * DD2
        #
        pattern = np.zeros((len(phi), len(theta)), dtype=complex)
        #
        for jj in range(len(phi)):
            for ii in range(len(theta)):
                pattern0 = weights * np.exp(1j * 2 * np.pi / self.lambda_ *
                                            (np.sin(phi[jj]) * np.cos(theta[ii]) * DD1 +
                                             np.sin(theta[ii]) * DD2 -
                                             np.sin(self.phi0) * np.cos(self.theta0) * DD1 -
                                             np.sin(self.theta0) * DD2))
                pattern[jj, ii] = np.sum(pattern0)
        #
        max_p = np.max(np.abs(pattern))
        pattern_dbw = 20 * np.log10(np.abs(pattern) / max_p + self.eps)
        #
        return pattern_dbw, theta, phi

    def drawWeight(self, data):
        plt.figure()
        plt.imshow(data)
        plt.axis('off')  # 这将隐藏x轴和y轴
        plt.show()



if __name__ == '__main__':
    print('SubarrayGA:')
    #
    # 初始化参数
    lambda_ = 1  # 波长
    d = 0.5  # 阵元间隔
    Ny = 40  # 方位阵元个数
    Nz = 40  # 俯仰阵元个数
    phi0 = 0  # 方位指向
    theta0 = 0  # 俯仰指向
    eps = 0.0001  # 底电平
    NA = 360  # 方位角度采样
    NE = 360  # 俯仰角度采样
    SLL = -60
    K = 9
    #
    subarrayGA = SubarrayGA(lambda_, Ny, Nz, d, phi0, theta0, NA, NE, eps, K)
    best_weight_sub = None
    best_msll = 0
    worst_weight_sub = None
    worst_msll = -80
    msll_list = []
    for i in range(0, 30):
        weights, weights_sub = subarrayGA.parse()
        pattern_dbw, theta, phi = subarrayGA.getPatternDbPlane(weights_sub)
        msll = psl_plane(NA, NE, theta0, phi0, pattern_dbw)
        msll_list.append(msll)
        if msll < best_msll:
            best_msll = msll
            best_weight_sub = weights_sub
        print("i:", i, ", msll:", msll, ", best_msll:", best_msll)
        if msll > worst_msll:
            worst_msll = msll
            worst_weight_sub = weights_sub
        print("i:", i, ", msll:", msll, ", worst_msll:", worst_msll)
    #
    print("best_weight_sub:")
    print(best_weight_sub)
    print("worst_weight_sub:")
    print(worst_weight_sub)
    #
    # pattern_dbw, theta, phi = subarrayGA.getPatternDbPlane(best_weight_sub)
    # pattern_dbw_worst, theta_worst, phi_worst = subarrayGA.getPatternDbPlane(worst_weight_sub)
    #
    subarrayGA.drawWeight(best_weight_sub)
    save_csv(best_weight_sub, "subarrayGA_40x40-9_30-3-3_60_2024-06-28.csv")
    save_csv(best_weight_sub, "../files/subarrayGA_40x40-9_30-3-3_60_2024-06-28.csv")
    subarrayGA.drawWeight(worst_weight_sub)
    save_csv(worst_weight_sub, "subarrayGA_40x40-9_30-3-3_60_worst_2024-06-28.csv")
    save_csv(worst_weight_sub, "../files/subarrayGA_40x40-9_30-3-3_60_worst_2024-06-28.csv")
    #
    msll_max_ga, msll_min_ga, msll_mean_ga, msll_std_ga = calculate_statistics(msll_list)
    print("[ga] psl_max=%.6f, psl_min=%.6f, psl_mean=%.6f, psl_std=%.6f" % (msll_max_ga, msll_min_ga, msll_mean_ga, msll_std_ga))
    #
    #
    #
    # print("weights_sub:")
    # print(weights_sub)
    # print("weights:")
    # print(weights)
    #
    # pattern_dbw, theta, phi = subarrayGA.getPatternDbPlane(weights_sub)
    #
    # subarrayGA.drawWeight(weights_sub)
    # save_csv(weights_sub, "subarrayNM_40x40-11_2024-06-24.csv")
    # save_csv(weights_sub, "../files/subarrayNM_40x40-11_2024-06-24.csv")
    #
    # msll = psl_plane(NA, NE, theta0, phi0, pattern_dbw)
    # print("msll:", msll)
    #
    #
    # # 示例数字集合
    # nums = [random.randint(1, 100) for _ in range(10)]
    #
    # # 运行遗传算法
    # best_solution = genetic_algorithm(nums)
    #
    # # 打印最佳解
    # group1 = [nums[i] for i in range(len(nums)) if best_solution[i] == 0]
    # group2 = [nums[i] for i in range(len(nums)) if best_solution[i] == 1]
    # print(f"Best grouping: {group1} and {group2}")
